#include<stdio.h>
#include<stdlib.h>
#define MAX_NUM_LENGTH 100
short *a,*b,*result;

//读取一个大数,输入的最后一个值应该保存在a[0]中，倒数第二个在a[1]中，...最先输入的应该保存在a[n-1]中
void ReadNUM(short *a){
    int pos = MAX_NUM_LENGTH - 1;
    char input = '\0';
    //确保数组不越界
    while(pos&&(input = getchar())!='\n'){
        //安全检查
        if('0'<=input&&input<='9'){
            input-='0';
            a[pos--] = (short)input;
        }else {
            printf("number format exception caused by letter: %c\n",input);
        }
    }
    int mov = 0;
    ++pos;
    //将用户的输入移到前面
    while(mov+pos<MAX_NUM_LENGTH){
        a[mov] = a[mov + pos];
        ++mov;
    }
    while(mov<MAX_NUM_LENGTH){
        a[mov++] = 0;
    }
}
//打印这个大数（观察效果）
void PrintNUM(short *a,int max_length){
    int edge = max_length-1;
    //去掉多余的0
    while(a[edge]==0) --edge;
    while(edge>=0) printf("%d",a[edge--]);
    printf("\n");
}
//大数加法
void superADD(const short *a,const short *b,short *result,int offset ,int max_length){
    int res_max_length = 2*MAX_NUM_LENGTH+1;
    short tmp = 0;
    int num_pos_ptr;
    //将上次计算的结果清零
    for(num_pos_ptr = 0;num_pos_ptr<res_max_length;++num_pos_ptr){
        result[num_pos_ptr] = 0;
    }
    num_pos_ptr = 0;
    //如果偏移量不为0，则a、b之间的顺序不可随意交换，否则结果可能出错
    while(num_pos_ptr<offset){
        result[num_pos_ptr] = a[num_pos_ptr];
        ++num_pos_ptr;
    }
    //此时 num_pos_ptr == offset
    while(num_pos_ptr<max_length){
        tmp = a[num_pos_ptr] + b[num_pos_ptr - offset];
        result[num_pos_ptr] += (tmp%10);
        result[num_pos_ptr+1] += (tmp/10 + result[num_pos_ptr]/10);
        //每一位的运算结果都可能大于10，因此要求余数
        result[num_pos_ptr]%=10;
        ++num_pos_ptr;
    }
    result[num_pos_ptr]%=10;
    //此时 num_pos_ptr == max_length，但b[]中还有一部分数据还要加到结果中
    while ((num_pos_ptr-offset) < max_length){
        result[num_pos_ptr] = b[num_pos_ptr-offset];
        ++num_pos_ptr;
    }
}

//大数乘法 可以基于大数加法实现
void superMUL(const short* a,const short *b,short *result,int max_length ){
    //存储a从0乘到9的结果，其中乘0的结果起占位作用，方便对齐
    //这个叫指针数组，也就是存放指针变量的数组，要和数组指针区分开
    short* tmp_res[10];
    int index;
    //0倍的结果无需存储
    tmp_res[0] = NULL;
    //动态分配内存
    for(index = 1;index<10;index++){
        tmp_res[index] = (short*)malloc((max_length+1)*sizeof(short));
    }
    //a的1倍直接确定
    for(index = 0;index<max_length;index++){
        tmp_res[1][index] = a[index];
    }
    tmp_res[1][index] = 0;
    //逐一计算2~9倍的结果
    for(index = 2;index<10;index++){
        superADD(tmp_res[index-1],tmp_res[1],result,0,max_length+1);
        int i;
        for(i=0;i<max_length+1;i++){
            tmp_res[index][i] = result[i];
        }
    }
    //----------------以上是准备工作--------------


    //核心步骤
    short temp_result[2*MAX_NUM_LENGTH + 1]={0};
    for(index=0;index<2*max_length+1;++index) result[index]=0;

    for(index=0;index<max_length;++index){
        if(b[index]==0) continue;
        superADD(result,tmp_res[b[index]],temp_result,index,MAX_NUM_LENGTH);
        int i;
        for(i=0;i<2*max_length+1;++i){
            result[i] = temp_result[i];
        }
    }

    //回收动态分配的内存(动态分配内存非常危险)
    for(index = 1;index<10;index++){
        //PrintNUM(tmp_res[index]);
        free(tmp_res[index]);
    }
}



 void super_fact(){
    //为运算分配空间
    a = (short*)calloc(MAX_NUM_LENGTH,sizeof(short));
    b = (short*)calloc(MAX_NUM_LENGTH,sizeof(short));
    result = (short*)calloc((2*MAX_NUM_LENGTH+1),sizeof(short));

//    ReadNUM(a);
//    ReadNUM(b);
    a[0] = 1;
    for(int i =1;i<=40;i++){
        b[0] = i%10;
        b[1] = i/10;
        superMUL(a,b,result,MAX_NUM_LENGTH);
        printf("%d! = ",i);
        PrintNUM(result,MAX_NUM_LENGTH);
        for(int j=0;j<MAX_NUM_LENGTH;j++){
            a[j] = result[j];
        }
    }

    free(a);
    free(b);
    free(result);
}

